package leetcode.L500;

import java.util.ArrayList;
import java.util.List;

public class EX93 {
    List<String> res;
    public List<String> restoreIpAddresses(String s) {
        res = new ArrayList<>();
        StringBuilder str = new StringBuilder();
        dfs(str,0,0,s);
        return res;
    }

    public void dfs(StringBuilder str,int len,int deep,String s){
        if(deep==4){
            if(len==s.length()){
                res.add(str.toString());
            }
            return;
        }

        for(int i = 1;i<=3;i++){
            if(len+i>s.length()){
                return;
            }
            String add = s.substring(len,len+i);
            if(!judge(add)){
                return;
            }
            if(deep!=0){
                str.append(".");
            }
            str.append(add);
            dfs(str,len+i,deep+1,s);
            str.delete(str.length()-i,str.length());
        }
    }

    public Boolean judge(String s){
        if(s.charAt(0)=='0'){
            int n = Integer.parseInt(s);
            if(n==0){
                return true;
            }else{
                return false;
            }
        }
        int n = Integer.parseInt(s);
        if(n>=0&&n<=255){
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        EX93 ex93 = new EX93();
        ex93.restoreIpAddresses("25525511135");
    }
}
